package offerbook.Code28_recallback_回溯_N皇后_排列;

/**
 * Created at 2019/10/25 0025 下午 10:02
 * 输入一个含有8个数字的数组，
 * 判断有没有可能把这8个数字分别放到正方体的8个顶点上（如下图所示），
 * 使得正方体上三组相对的面上的4个顶点的和都相等。
 *
 * 思路：
 * 相当于先得到a1、a2、a3、a4、a5、a6、a7和a8这8个数字的所有排列，
 * 然后判断有没有某一个的排列复合题目所给定的条件，
 * 即a1 + a2 + a3 + a4 == a5 + a6 + a7 + a8，
 * a1 + a3 + a5 + a7 == a2 + a4 + a6 + a8，
 * 并且a1 + a2 + a5 + a6 == a3 + a4 + a7 + a8。
 */
public class Code28_IsEqual {


    public static void permutation(int[] array) {
        if (array == null || array.length != 8) {
            return;
        }
        boolean flag = permutation(array, 0);

        if (flag) {
            System.out.println("ok");
        } else {
            System.out.println("sorry");
        }

    }

    /**
     * 求array的全排列，判断所有的重排列是否满足结果
     */
    private static boolean permutation(int[] array, int index) {

        if(index == array.length -1){
            //现在array已经被重排序完毕了，判断是否满足要求
            return isEqual(array);
        }

        for (int i = index; i < array.length ; i++) {
            swap(array,i,index);
            permutation(array,index+1);
            swap(array,index,i);
        }
        return false;
    }


    /**
     * 判断是否满足条件
     */
    private static boolean isEqual(int[] array) {
        if (array == null) {
            return false;
        }
        /*
         * a1 + a2 + a3 + a4 == a5 + a6 + a7 + a8
         * a1 + a3 + a5 + a7 == a2 + a4 + a6 + a8
         * a1 + a2 + a5 + a6 == a3 + a4 + a7 + a8
         */
        int result1 = array[0] + array[1] + array[2] + array[3];
        int result2 = array[4] + array[5] + array[6] + array[7];
        int result3 = array[0] + array[2] + array[4] + array[6];
        int result4 = array[1] + array[3] + array[5] + array[7];
        int result5 = array[0] + array[1] + array[4] + array[5];
        int result6 = array[2] + array[3] + array[6] + array[7];

        return result1 == result2 && result3 == result4 && result5 == result6;
    }


    private static void swap(int[] array, int index, int i) {
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}
